#include <cstdio>
#include <cstring>
#define MAXN 105
#define INF 10000000

int n,m;

int edge[MAXN][MAXN];
int s[MAXN];
int dist[MAXN];

void dijkstra()
{
    for (int i=0; i<n; i++)
    {
        dist[i]=edge[0][i];
        s[i]=0;
    }
    s[0]=1;
    dist[0]=0;
    for (int i=0; i<n-1; i++)
    {
        int min=INF,u=0;
        for (int j=0; j<n; j++)
        {
            if( !s[j] && dist[j]<min)
            {
                u=j;
                min=dist[j];
            }
        }
        s[u]=1;
        for (int k=0; k<n; k++)
        {
            if (!s[k] && edge[u][k]<INF && dist[k]>edge[u][k]+dist[u])
                dist[k]=edge[u][k]+dist[u];
        }
    }
}

int main()
{
    freopen("in.txt","r",stdin);
    while (scanf("%d%d",&n,&m))
    {
        int u,v,w;
        int i,j;
        if (n==0&&m==0)    break;
        for(i=0; i<=n; i++)
        {
            for(j=0; j<=i; j++)
            {
                if (i==j) edge[i][j]=0;
                edge[i][j]=INF;
                edge[j][i]=INF;
            }
        }
        for (i=0; i<m; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            u--;
            v--;
            if ( w < edge[u][v] )
            {
                edge[u][v]=w;
                edge[v][u]=w;
            }
        }
        dijkstra();
        printf("%d\n",dist[n-1]);
    }
}
